package basic.basic_class04;

/**
 * 判断一个树是否为平衡二叉树
 */
public class Code_06_IsBalancedTree {

    // 节点类
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    // 返回结果的实体类
    public static class ResultData{
        boolean isAvl;   // 是否为平衡二叉树
        int height;      // 当前树的高度

        public ResultData(boolean isAvl, int height){
            this.isAvl = isAvl;
            this.height = height;
        }
    }

    // 判断head树是否是AVL
    public static boolean isBalance(Node head) {
        ResultData data = isBalanceTree(head);
        return data.isAvl;
    }

    public static ResultData isBalanceTree(Node head) {
        if(head == null) {
            return new ResultData(true,0);
        }
        ResultData leftData = isBalanceTree(head.left);
        if(!leftData.isAvl){
            return new ResultData(false,0);
        }
        ResultData rightData = isBalanceTree(head.right);
        if(!rightData.isAvl){
            return new ResultData(false,0);
        }
        if(Math.abs(leftData.height - rightData.height) > 1){
            return new ResultData(false,0);
        }
        return new ResultData(true,Math.max(leftData.height,rightData.height) + 1);
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        System.out.println(isBalance(head));

    }
}
